# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        self.p, self.q, self.mid_set = p.val, q.val, {p.val, q.val}
        try:
            self.search(root)
        except:
            return self.res

    def search(self, root: TreeNode):
        left = self.search(root.left) if root.left else False
        right = self.search(root.right) if root.right else False
        if left + right + (root.val in self.mid_set) >= 2:
            self.res = root
            raise StopAsyncIteration
        return left or right or root.val in self.mid_set
